package leetcode1;

public class Day13 {
    public static void main(String[] args) {
        int[] a = {5,1,2,3,4};
        int[] b = {4,4,1,5,1};
        canCompleteCircuit(a,b);
    }

    public static int canCompleteCircuit(int[] gas, int[] cost) {

        int n = gas.length;
        if(n==1 && gas[0] - cost[0] >= 0) return 0;
        for(int i=0;i<n;i++) {//枚举所有的起点
            if(gas[i] - cost[i] > 0) {//可以出发
                int tmp = 0;
                int j=i,pos=i;//遍历加油站,记录初始位置
                if(j==n-1) {//起点为最后一个位置
                    tmp = gas[i]-cost[i];
                    j=0;//从起始点开始
                }
                while(tmp>=0 && j<n) {
                    tmp += gas[j];//获取汽油
                    tmp -= cost[j];//消耗汽油到达下一站
                    j++;
                }
                if(tmp<0) continue;//不满足起点
                if(j==pos) return pos;//满足起点
                j=0;
                while(tmp>=0 && j<n) {
                    tmp += gas[j];//获取汽油
                    tmp -= cost[j];//消耗汽油到达下一站
                    j++;
                }
                if(tmp>=0) return pos;
            }
        }
        return -1;
    }

}
